import java.util.*;

public class Test {
    // 题目1：迷宫中离入口最近的出口
    boolean[][] vis ;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int nearestExit(char[][] maze, int[] e) {
        int m = maze.length;
        int n = maze[0].length;
        vis = new boolean[m][n];

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{e[0], e[1]});
        vis[e[0]][e[1]] = true;
        int step = 0;

        while(!q.isEmpty()){
            int sz = q.size();
            step++;
            for(int j = 0; j < sz; j++){
                int[] t = q.poll();
                int a = t[0], b = t[1];
                for(int i = 0; i < 4; i++){
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.') {
                        if(x == 0 || x == m - 1 || y == 0 || y == n - 1){
                            return step;
                        }
                        q.offer(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }

        }
        return -1;
    }


    // 题目2：最小基因变化
    public static int minMutation(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)) return 0;
        Set<String> bankHash = new HashSet<>();
        for(String s : bank){
            bankHash.add(s);
        }
        if(!bankHash.contains(endGene)){
            return -1;
        }
        Set<String> vis = new HashSet<>();
        char[] change = {'A','T','C','G'};
        Queue<String> q = new LinkedList<>();
        vis.add(startGene);
        q.offer(startGene);
        int step = 0;
        while(!q.isEmpty()){
            step++;
            int sz = q.size();
            for(int k = 0; k < sz; k++){
                String s = q.poll();
                for(int i = 0; i < 8; i++){
                    char[] temp = s.toCharArray();
                    for(int j = 0; j < 4; j++){
                        temp[i] = change[j];
                        String ss = new String(temp);
                        if(bankHash.contains(ss) && !vis.contains(ss)){
                            if(ss.equals(endGene)) return step;
                            q.offer(ss);
                            vis.add(ss);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String start = "AACCGGTT";
        String end = "AACCGGTA";
        String[] bank = {"AACCGGTA"};
        int ret = minMutation(start, end, bank);
        System.out.println(ret);
    }

    // 题目3：单词接龙
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)){
            return 0;
        }
        Set<String> list = new HashSet<>();
        for(String s : wordList){
            list.add(s);
        }
        if(!list.contains(endWord)){
            return 0;
        }

        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        Set<String> vis = new HashSet<>();
        vis.add(beginWord);
        int step = 1;
        while(!q.isEmpty()){
            step++;
            int sz = q.size();
            for(int i = 0; i < sz; i++){
                String s = q.poll();
                for(int j = 0; j < beginWord.length(); j++){
                    char[] temp = s.toCharArray();
                    for(char ch = 'a' ; ch <= 'z'; ch++){
                        temp[j] = ch;
                        String ss = new String(temp);
                        if(!vis.contains(ss) && list.contains(ss)){
                            if(ss.equals(endWord)) return step;
                            vis.add(ss);
                            q.offer(ss);
                        }
                    }
                }
            }
        }
        return 0;
    }

    // 题目4：为高尔夫比赛砍树
    int m, n;
    public int cutOffTree(List<List<Integer>> forest) {
        List<int[]> trees = new LinkedList<>();
        m = forest.size();
        n = forest.get(0).size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(forest.get(i).get(j) > 1){
                    trees.add(new int[]{i, j});
                }
            }
        }
        Collections.sort(trees, (a, b) ->{
            return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);
        });

        int sz = trees.size();
        int bx = 0, by = 0;
        int ret = 0;
        for(int[] tree : trees){
            int x = tree[0], y = tree[1];
            int step = bfs(forest, bx, by, x, y);
            if(step == -1) return -1;
            ret += step;
            bx = x;
            by = y;
        }
        return ret;
    }

//    int[] dx = {0, 0, 1, -1};
//    int[] dy = {1, -1, 0, 0};
    public int bfs(List<List<Integer>> forest, int bx,int by,int ex,int ey){
        if(bx == ex && by == ey) return 0;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        q.offer(new int[]{bx, by});
        vis[bx][by] = true;
        int step = 0 ;
        while(!q.isEmpty()){
            step++;
            int sz = q.size();
            for(int k = 0; k < sz; k++){
                int[] t = q.poll();
                int a = t[0], b = t[1];
                for(int i = 0; i < 4; i++){
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && forest.get(x).get(y) != 0){
                        if(x == ex && y == ey){
                            return step;
                        }
                        q.offer(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }

    // 题目5：N 字形变换
    public String convert(String s, int numRows) {
        if(numRows < 2){
            return s;
        }

        List<StringBuilder> list = new LinkedList<>();
        for(int i = 0; i < numRows; i++){
            list.add(new StringBuilder());
        }

        int i = 0;
        int flag = -1;
        for(char x : s.toCharArray()){
            list.get(i).append(x);
            if(i == 0 || i == numRows - 1){
                flag = -flag;
            }
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : list){
            res.append(row);
        }
        return res.toString();
    }
}
